#define _CRT_SECURE_NO_WARNINGS 1
const int N = 1e6 + 1000;
int h[N], e[N * 2], ne[N * 2], idx;
int st[N];


void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

class Solution {
public:
    void dfs(TreeNode* root) {
        if (root == nullptr)return;
        if (root->left) {
            int a = root->val;
            int b = root->left->val;
            add(a, b);
            add(b, a);
            dfs(root->left);
        }
        if (root->right) {
            int a = root->val;
            int b = root->right->val;
            add(a, b);
            add(b, a);
            dfs(root->right);
        }
    }

    int bfs(int start) {
        queue<int> q;
        q.push(start);
        int res = 0;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int t = q.front();
                q.pop();
                st[t] = 1;
                // cout<<t<<":";
                for (int j = h[t]; j != -1; j = ne[j]) {
                    int k = e[j];

                    if (!st[k]) {
                        //cout<<k<<" ";
                        q.push(k);
                        st[k] = 1;
                    }
                }
                //  cout<<endl;
            }
            res++;
            //  cout<<res<<"----"<<endl;
        }
        return res - 1;
    }
    int amountOfTime(TreeNode* root, int start) {
        memset(h, -1, sizeof h);
        memset(e, 0, sizeof e);
        memset(ne, 0, sizeof ne);
        memset(st, 0, sizeof st);
        dfs(root);
        return bfs(start);
    }
};